package com.liang.leetcode.list;

/**
 * 707.设计链表：
 * <a href="https://leetcode.cn/problems/design-linked-list/">https://leetcode.cn/problems/design-linked-list/</a>
 * 题意：
 * 在链表类中实现这些功能：
 * get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
 * addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
 * addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
 * addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
 * deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
 */
public class List02_MyLinkedList {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();

        myLinkedList.addAtHead(1);
        myLinkedList.printLinkedList();             // 链表变为 1->null

        myLinkedList.addAtTail(3);
        myLinkedList.printLinkedList();             // 链表变为 1->3->null

        myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
        myLinkedList.printLinkedList();             // 链表变为 1->2->3->null

        System.out.println(myLinkedList.get(1));    // 返回 2
        myLinkedList.deleteAtIndex(0);              // 链表变为 2->3->null
        myLinkedList.printLinkedList();

        System.out.println(myLinkedList.get(1));     // 返回 3
    }
}

// 设计链表：单链表
class MyLinkedList {

    // 链表元素个数
    int size;

    // 虚拟头结点
    ListNode_List02 head;

    /**
     * 链表初始化
     */
    MyLinkedList() {
        size = 0;
        head = new ListNode_List02(0); // head 指向虚拟头结点
    }

    /**
     * 获取链表中下标为 index 结点的值，index 从 0 开始，如果下标无效，则返回 -1。
     * @param index
     * @return
     */
    public int get(int index) {
        // 如果index非法，返回-1
        if (index < 0 || index >= size) {
            return -1;
        }

        // 获取第一个存储元素的结点，即链表头结点next指向的结点
        ListNode_List02 currentNode = head.next;

        // 从第一个存储元素的结点开始遍历
        for (int i = 0; i < index; i++) {
            currentNode = currentNode.next;
        }

        // 返回 index 结点的值
        return currentNode.val;
    }

    /**
     * 将一个值为 val 的结点插入到链表中第一个元素之前。
     * 在插入完成后，新结点会成为链表的第一个结点。
     * @param val
     */
    public void addAtHead(int val) {
        //在链表最前面插入一个节点，等价于在第0个元素前添加
        addAtIndex(0, val);
    }

    /**
     * 将一个值为 val 的结点追加到链表中作为链表的最后一个元素。
     * @param val
     */
    public void addAtTail(int val) {
        //在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
        addAtIndex(size, val);
    }

    /**
     * 将一个值为 val 的结点插入到链表中下标为 index 的结点之前。
     * 如果 index 等于链表的长度，那么该结点会被追加到链表的末尾。
     * 如果 index 比长度更大，该结点将不会插入到链表中。
     * @param index 插入结点的下标
     * @param val   要插入结点的值
     */
    public void addAtIndex(int index, int val) {
        // index 大于链表长度，直接返回
        if (index > size) {
            return;
        }
        // index 小于链表长度，重置为 0
        if (index < 0) {
            index = 0;
        }

        // 更新size
        size++;

        // 获取要插入结点的前驱结点，方便插入操作
        ListNode_List02 preNode = head;
        // 找到结点插入的位置，有虚拟头结点，index 不用 -1
        for (int i = 0; i < index; i++) {
            preNode = preNode.next;
        }

        // 创建新结点并插入
        ListNode_List02 addNode = new ListNode_List02(val);
        addNode.next = preNode.next;
        preNode.next = addNode;
    }

    /**
     * 如果下标有效，则删除链表中下标为 index 的结点
     * @param index
     */
    public void deleteAtIndex(int index) {
        // 判断 index 是否合法
        if (index < 0 || index >= size) {
            return;
        }

        // 每次删除或添加结点操作都要更新 size
        size--;

        // 删除头结点
        // 使用虚拟头结点后，统一了各种位置上的删除操作，因此可省略判断index是否为第一个结点步骤
        // if (index == 0) {
        //     // 将第一个存储元素的结点变为虚拟结点，head重新指向该虚拟结点
        //     head = head.next;
        //     // 删除完头结点后要返回
        //     return;
        // }

        // 需要获取删除结点前驱结点，防止链表断裂
        ListNode_List02 preNode = head;
        for (int i = 0; i < index; i++) {
            preNode = preNode.next;
        }

        // 删除结点
        preNode.next = preNode.next.next;
    }

    /**
     * 打印链表元素
     */
    public void printLinkedList() {
        // 指向第一个存储元素的结点
        ListNode_List02 currentNode = head.next;
        // 打印链表结点元素
        for (int i = 0; i < size; i++) {
            System.out.print(currentNode.val + "->");
            currentNode = currentNode.next;
        }
        System.out.println("null");
    }
}

// 单链表存储结构
class ListNode_List02 {
    // 结点存储的值
    int val;

    // 指向下一结点的指针
    ListNode_List02 next;

    // 无参构造
    public ListNode_List02() {

    }

    // 有参构造
    public ListNode_List02(int val) {
        this.val = val;
    }
}